package easy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Solution_628 {

    public int maximumProduct(int[] nums) {
        List<Integer> lt = new ArrayList<>();
        List<Integer> gt = new ArrayList<>();
        for (int num : nums) {
            if (num > 0) {
                gt.add(num);
            } else if (num < 0) {
                lt.add(num);
            }
        }
        Collections.sort(lt);
        Collections.sort(gt);

        int max = Integer.MIN_VALUE;
        boolean existZero = nums.length > lt.size() + gt.size();

        // 三正
        if (gt.size() >= 3) {
            max = Math.max(gt.get(gt.size() - 1) * gt.get(gt.size() - 2) * gt.get(gt.size() - 3), max);
        }

        // 两正
        if (gt.size() >= 2 && lt.size() >= 1) {
            max = Math.max(gt.get(0) * gt.get(1) * lt.get(lt.size() - 1), max);
        }

        // 一正
        if (gt.size() >= 1 && lt.size() >= 2) {
            max = Math.max(lt.get(0) * lt.get(1) * gt.get(gt.size() - 1), max);
        }
        // 全负
        if (lt.size() >= 3) {
            max = Math.max(lt.get(lt.size() - 1) * lt.get(lt.size() - 2) * lt.get(lt.size() - 3), max);
        }
        if (existZero) {
            return Math.max(0, max);
        }
        return max;
    }

    public static void main(String[] args) {
        Solution_628 model = new Solution_628();

        System.out.println(model.maximumProduct(new int[]{1,2, 3 , 5}));
        System.out.println(model.maximumProduct(new int[]{-1,-5, 0, 1,2, 3 , 5}));
        System.out.println(model.maximumProduct(new int[]{-1,-5, 3 , 5}));
        System.out.println(model.maximumProduct(new int[]{-1,-5, 0, 3 , 5}));
        System.out.println(model.maximumProduct(new int[]{-1,-5, 5}));
        System.out.println(model.maximumProduct(new int[]{-1,-5, 0, 5}));
        System.out.println(model.maximumProduct(new int[]{-1,-5, -4, -3}));
        System.out.println(model.maximumProduct(new int[]{-1,-5, -4, -3, 0}));
        System.out.println(model.maximumProduct(new int[]{-100, -98, -1, 2, 3, 4}));
    }
}
